#define MAX(a, b) (((a) > (b)) ? (a) : (b))

// step 1# 求所有石头重量的总和
int getSum(int *stones, int stoneSize) {
    int sum = 0, i;
    for (i = 0; i < stoneSize; ++i)
        sum += stones[i];
    return sum;
}

// step 2# 主函数，计算最后剩余石头的最小重量
int lastStoneWeightII(int* stones, int stonesSize){
    // step 2.1# 计算所有石头的总重量
    int sum = getSum(stones, stonesSize);

    // step 2.2# 目标是把石头分成两堆，尽量接近sum/2
    int target = sum / 2;
    int i, j;

    // step 2.3# 初始化一维dp数组，dp[j]表示容量为j时能取得的最大重量
    int *dp = (int*)malloc(sizeof(int) * (target + 1));
    memset(dp, 0, sizeof(int) * (target + 1));

    // step 2.4# 初始化：如果第一个石头能放下，填进去
    for (j = stones[0]; j <= target; ++j)
        dp[j] = stones[0];
    
    // step 2.5# 遍历每块石头
    for (i = 1; i < stonesSize; ++i) {
        // step 2.5.1# 逆序遍历背包容量（保证每块石头只能用一次）
        for (j = target; j >= stones[i]; --j)
            // step 2.5.2# 递推公式：取放或者不放当前石头后的最大重量
            dp[j] = MAX(dp[j], dp[j - stones[i]] + stones[i]);
    }

    // step 2.6# 返回最终的最小可能重量：
    // 总重量减去两倍的较大堆重量
    return sum - dp[target] - dp[target];
}
